package com.example

import scala.collection.mutable.ArrayBuffer

// 定义网格单元状态，Empty：可通行。Obstacle：不可通行。
sealed trait CellState
case object Empty extends CellState
case object Obstacle extends CellState

// 定义正方形矩形区域及其相交判断操作
case class Bounds(x: Int, y: Int, size: Int) {
  def intersects(other: Bounds): Boolean = {
    !(x > other.x + other.size ||
      x + size < other.x ||
      y > other.y + other.size ||
      y + size < other.y)
  }
}

// 定义四叉树节点基类。
sealed trait QuadTree

// 定义叶子节点
case class Leaf(state: CellState, bound: Bounds) extends QuadTree {
  var neighbors: ArrayBuffer[Leaf] = ArrayBuffer.empty

  def center: (Int, Int) = (this.bound.x + this.bound.size / 2, this.bound.y + this.bound.size / 2)
  // 计算和本节点相交的邻居，计算邻居时会忽略不可通行的点，即(1)黑点没有邻居(2)白点也没有黑点邻居。
  def findNeighbors(root: QuadTree): Unit = {
    state match {
      case Empty =>
        root match {
          case n: Node =>
            findNeighbors(n.nw)
            findNeighbors(n.ne)
            findNeighbors(n.sw)
            findNeighbors(n.se)
          case n: Leaf =>
            if (n.state == Empty && n != this && this.bound.intersects(n.bound))
              this.neighbors += n
        }
      case _ =>
    }
  }
}

// 定义父节点
class Node(var nw: QuadTree, var ne: QuadTree, var sw: QuadTree, var se: QuadTree, var bound: Bounds) extends QuadTree
